package main.java.middle;

/**
 * @Author: 郑国荣
 * @Date: 2023-08-18-17:28
 * @Description: 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数
 */
public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int len=coins.length;
        if (amount==0 || len==0) return 0;
        int[] arr=new int[len];
        int minCounts=1000;
        for (int i = 0; i < len; i++) {
            int tempAmount=amount;
            if (tempAmount>coins[i]){
                int currentCount=0;
                for (int j = 0; j < len; j++) {
                    int index=1;
                    while (coins[j]*index < amount){
                        tempAmount-=arr[j]*index;
                        index++;
                        currentCount+=index;
                    }
                }
                if (tempAmount ==0){
                    minCounts = Math.min(currentCount,minCounts);
                }
            }
        }
        return minCounts;
    }

    public static void main(String[] args) {
        int[] a={186,419,83,408};
        System.out.println(coinChange(a, 6249));
    }
}
